home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / byacc 1.8.2 / warshall.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-04  |  1.3 KB  |  93 lines  |  [TEXT/R*ch]
  1. #include "defs.h"
  2.  
  3. #if __STDC__
  4. static void transitive_closure(unsigned *R, int n)
  5. #else
  6. static void transitive_closure(R, n)
  7. unsigned *R;
  8. int n;
  9. #endif
  10. {
  11.     register int rowsize;
  12.     register unsigned mask;
  13.     register unsigned *rowj;
  14.     register unsigned *rp;
  15.     register unsigned *rend;
  16.     register unsigned *ccol;
  17.     register unsigned *relend;
  18.     register unsigned *cword;
  19.     register unsigned *rowi;
  20.  
  21.     rowsize = WORDSIZE(n);
  22.     relend = R + n*rowsize;
  23.  
  24.     cword = R;
  25.     mask = 1;
  26.     rowi = R;
  27.     while (rowi < relend)
  28.     {
  29.     ccol = cword;
  30.     rowj = R;
  31.  
  32.     while (rowj < relend)
  33.     {
  34.         if (*ccol & mask)
  35.         {
  36.         rp = rowi;
  37.         rend = rowj + rowsize;
  38.         while (rowj < rend)
  39.             *rowj++ |= *rp++;
  40.         }
  41.         else
  42.         {
  43.         rowj += rowsize;
  44.         }
  45.  
  46.         ccol += rowsize;
  47.     }
  48.  
  49.     mask <<= 1;
  50.     if (mask == 0)
  51.     {
  52.         mask = 1;
  53.         cword++;
  54.     }
  55.  
  56.     rowi += rowsize;
  57.     }
  58. }
  59.  
  60. #if __STDC__
  61. void reflexive_transitive_closure(unsigned *R, int n)
  62. #else
  63. void reflexive_transitive_closure(R, n)
  64. unsigned *R;
  65. int n;
  66. #endif
  67. {
  68.     register int rowsize;
  69.     register unsigned mask;
  70.     register unsigned *rp;
  71.     register unsigned *relend;
  72.  
  73.     transitive_closure(R, n);
  74.  
  75.     rowsize = WORDSIZE(n);
  76.     relend = R + n*rowsize;
  77.  
  78.     mask = 1;
  79.     rp = R;
  80.     while (rp < relend)
  81.     {
  82.     *rp |= mask;
  83.     mask <<= 1;
  84.     if (mask == 0)
  85.     {
  86.         mask = 1;
  87.         rp++;
  88.     }
  89.  
  90.     rp += rowsize;
  91.     }
  92. }
  93.